\documentclass[11pt]{article}

\usepackage{aaai}
\usepackage{times}
\usepackage{helvet}
\usepackage{courier}
\usepackage[vlined,ruled]{algorithm2e}
\usepackage{graphics}
\usepackage{colordvi,epsfig,multirow,fancybox,psfig,amsmath,amssymb}
\usepackage{subfigure}


%\setlength{\voffset}{-0.4in}

\newcommand{\nop}[1]{}

\newtheorem{defn}{Definition}
\newtheorem{ex}{Example}
\newtheorem{theorem}{Proposition}
\def\qed{\hspace*{\fill} $\blacksquare$}


\title{\LARGE\bf Plan-A: Finding the Minimal Costs Solution}

%\author{}

\date{}


\begin{document}
\maketitle


\begin{abstract} AAAAAAAAAAA
Planning as satisfiability, represented by SATPlan, can find plans
with the shortest makespan for classical planning. However, it has
been deemed a limitation of SAT-based approaches for delivering
optimality regarding metrics other than the makespan.

In this paper, we propose an algorithm, based on the SAT-based
framework, that can find plans with minimal total action costs. The
idea is to optimally solve SAT instances at different levels, based
on certain optimality criteria. Bounding and pruning techniques are
proposed and integrated with the standard DPLL algorithm to reduce
the search cost. Extensive experimental results on various planning
domains show that the proposed algorithm can find optimal plans
without only little additional time cost comparing to the original
SAT-based planners. Further, it gives much better performance than
SATPlan$^{\prec}$, another recently proposed SAT-based planner that
minimizes the action costs.
\end{abstract}



\section{Introduction}
%Q.Lv can you add some Introducing about MaxPlan?
%R.Huang We don't need to discuss Maxplan. It is not necessary.


%R.Huang Why the experiments are sometimes mentioned as "XX on IPCs", but sometimes "XX on IPC5" instead? I am confused.

%R.Huang A reminder, always use `` '' instead of " ", they are different

%R.Huang I prefer "Blocking Clause " to "block clause", what do you think?

SATPlan\cite{Kautz04}~\cite{Kautz06}, along with its earlier version
BlackBox~\cite{Kautz96}, are the most well-known planners under the
paradigm of planning as satisfiability.
%SATPlan won the First Place
%prize in the optimal track of the fourth and fifth International
%Planning Competition(IPC)~\ref{}.
Given a planning problem , SATPlan first generates a corresponding
SAT formulation with a fixed ``makespan" $n$ starting from 1, then
checks for satisfiability using third party SAT solvers. The
 planner stops if the formulation of a particular $n$ is satisfiable,
and thus a plan is found, otherwise increases $n$ and keeps
searching. Most of the SAT based planners follow this framework and
generate solutions optimal in makespan. Nevertheless, this strategy
 recently turns out to has limitations, as the interests in the
 optimality of action-cost keeps increasing nowadays.


%SATPlan$^{\prec}$ ~\cite{Giu07}, a variation of SATPlan, makes a
% large step towards the elimination of SATPlan's limitations.
%It can return plans with minimal number of actions giving the
%optimal makespan. SATPlan$^{\prec}$ ensures minimal number of
%actions by splitting the set of actions in $\Pi_n$ and assigning
%them to FALSE. Let the set of atoms $S$ to be the set that should be
%optimized, i.e., the set of actions in $\Pi_n$. If the optimality is
%to be performed under subset inclusion, it suffices to
%``preferentially" splits on the atom in $S$, and assign it to FALSE.
%The resulting satisfying assignment $\mu$ of $\Pi_n$ is guaranteed
%to contain the minimal number of atoms, leading to a plan with the
%minimal number of actions~\cite{Giu07}.
%R.Huang This paragraph of review need to be significantly rewritten.


SATPlan$^{\prec}$ ~\cite{Giu07}, a variation of SATPlan, makes a
significant step towards the elimination of SATPlan's limitations.
It can return plans with minimum number of actions giving the
optimal makespan. This is achieved by integrating the OPTSAT solver.
OPTSAT~\cite{Giu:JELIA-06} is a tool for solving SAT related
optimization problems based on the state-of-the-art SAT solver
MiniSat. Differently from our modified MiniSat systems, OPTSAT does
not follow a branch$\&$bound schema (whenever a solution is found,
the search goes on looking for another solution with a lower cost),
but it solves the optimization problems by imposing a partial
ordering on the literals to branch on. Given a SAT formula $\Pi_n$
and a subset S of the variables in $\Pi_n$, OPTSAT can return an
``optimal" solution that minimizes the atom in $S$ assigned to TRUE.
%R.Huang What does minimize the atom mean? Is this a typo?



SATPlan$^{\prec}$ did make improvements in finding solutions with
better quality regarding action-cost, however, it actually still
cannot guarantee the optimality. In this paper, we propose another
alternative approach to search for solutions near-optimal in
action-cost. According to the experimental results, we will see that
Plan-A outperforms SATPlan$^{\prec}$ by solving more instances, for
 which many of them have better quality. As expected, comparing to Maxplan
 and SATPlan, it also obtains solutions of much better quality but with
 longer solving time as a tradeoff.


This paper is organized as follows. First of all, we will introduce
the the DPLL-OPT algorithm. Instead of seeking for a satisfying
solution, it searches the whole space of a SAT problem minimizing
the subjective function, with aid of additional pruning techniques.
Consequently, based on the interesting observations that in most
planning problems, the action-cost optimal solutions exists right in
the time level that the first satisfying solution is found, we try
to enumerate all the possible solutions within limited time levels
to get a better solution using the DPLL-OPT algorithm.


\section{Plan-A Planning Algorithm}

In Plan-A, we firstly encode a planning problem into SAT problems,
and then call DPLL-OPT to solve them.

%***********************************************************************
%                             main procedure of Plan-A
%***********************************************************************

\begin{algorithm}[t]
\label{mainprocedure} \linesnumbered \caption{Plan-A() }

\KwIn{planning problem $P$}

\KwOut{solution with minimal number of actions}

generate domain transition graphs\;

generate londex constraints\;

$layer\leftarrow 1$\;

\While{$layer\leq MaxLayer$}{
    encode $P$ of $layer$ to SAT problem $S$ \;
    DPLL-OPT($S$)\;
    \If{found a solution}{
        \ForEach{layer of the next three layers}{
            encode $P$ of $layer$ to SAT problem $S$\;
            DPLL-OPT($S$)\;
        }
        break\;
    }
    layer++\;
}
\end{algorithm}
%R.Huang Make sure this algorithm is correct. Why these two loop is nested? I don't know. Just want to make sure.


ALWAYS EXPLAIN THE ALGORITHM LINE BY LINE!


%R.Huang I believe "block clause" is supposed to be "blocking clause"

We will not return SAT when found a solution, but instead we add a
blocking clause to the clause database.  Then we do backtracking to
search for other solutions with less cost. According to the
experimental results, the minimum cost solution is mostly at the
layer which does not exceed the third layer after the first
satisfying solution's layer. Therefore, once a satisfying solution
is found, we keep searching for a limited number of time layers to
see if there is better solutions.


The key part of Plan-A is to find out solutions optimal in
action-cost for different makespans. We will discuss it in the next
section.


\section{Optimizing the SAT Problems}

Most modern SAT solvers are under the DPLL algorithm~\ref{}
framework, along with other helping techniques like clause learning,
watching list and so on. Instead of finding a satisfying solution
for SAT problems, in this section we introduce DPLL-OPT, an approach
that solves SAT problem minimizing a particular objective function.


%R.Huang  We may need to have some reference here with respect to DPLL;

\subsection{The standard DPLL algorithm}


In this section, we will review the typical basic modern SAT solving
algorithm which uses the DPLL framework.

%R.Huang I think all the prefix solver- of each procedure is unnecessary; I removed all of them;

%R.Huang the whole section of how to use Mini-SAT is nonsense;

%Public interface of MiniSat-solver:
%
%\hspace{0.5cm}\emph{var} \hspace{0.5cm} $newVar$()
%
%\hspace{0.5cm}\emph{bool}\hspace{0.5cm} solver$_-$addClause()
%
%\hspace{0.5cm}\emph{bool}\hspace{0.5cm}solver$_-$simplifyDB()
%
%\hspace{0.5cm}\emph{bool}\hspace{0.5cm}solver$_-$solve()
%
%\hspace{0.5cm}\emph{veci}\hspace{0.5cm}$model$\hspace{0.5cm}\emph{-If
%found, this vector has the model.}
%
%For the MiniSat-solver~\cite{Niklas04}, the interface is used in the
%following way:

%Solver reads the CNF file, and add clauses by calling
%solver$_-$addClause(), in which newVar() may be called to introduce
%new variables.

%Trivial conflicts, such as two unit clauses \{$x$\} and
%\{$\overline{x}$\} being added, can be detected by
%solver$_-$addClause(), in which case it returns FALSE. If no such
%trivial conflict is detected during the clause insertion phase,
%solver$_-$solve() is called, and returns UNSAT if the problem is
%unsatisfiable, and SAT if it is satisfiable, in which case the model
%can be read from the public vector $model$.
%
%The addClause() method can detect unit clause and add the literal of
%it to propagation queue, which is a set of literals(unit
%information) kept by the propagation routine. If the clause is not a
%unit clause, it will be added into two-literal watcher list and
%clause database.
%
%The simplifyDB() method can be called to simplify the set of problem
%constraints database only in the root-level of search.


%R.Huang I doubt those commented above is necessary or not...
%R.Huang This is not a user manual of MiniSAT, so try to avoid rely on MiniSAT for the algorithm description;

%***********************************************************************
% *******************               main procedure of DPLL
%***********************************************************************
\begin{algorithm}[t]
\label{solve} \linesnumbered \caption{ DPLL() }

\KwIn{ SAT problem $S$ }

\KwOut{ a satisfying solution }

{initialize the solver\;}

\While{ $true$ }{

    do propagation\;

    \If{conflict found}{

        $learnt \leftarrow$ analyze($conflict$)\;
        add $learnt$ to the clause database\;

        \eIf{top-level conflict found}{
            return UNSAT\;
        }{
           do backtracking\;

%R.Huang In my opinion, try to write the pseudo-code in a more natural way, i.e. avoid using too many procedure calls
%R.Huang (unless have sort of argument like analyze())

       }
    }\Else{

        \eIf{all variables assigned}{
            return SAT\;
        }{
            decide()\;
%What does decide() do?

        }
    }
}
\end{algorithm}


%R.Huang I still don't know what is "implicit conflict-driven", is this an term some other's paper? Pls refer to it.

Procedure DPLL() is of conflict-driven and it is somewhat implicit.
After the initialization (Line ), the while loop of the procedure
will start by propagating a literal $p$ in propagation queue (Line
), otherwise it calls $decide$() to select an unassigned variable
$x$, assumes it to be $true$ and inserts the corresponding literal
to propagation queue. The literal $p$'s consequence will then be
propagated, resulting in more variables assignments. They have the
same decision level with literal p. The decision level in which the
assignments are made before the first assumption is called the
top-level (decision level 0).

%R.Huang Description of an algorithm should be conduct in a line-by-line way, indicating each sentence with the corresponding line number(s), like above;

The while loop keeps running until either a conflict occurs (Line ),
or all the variables are assigned, in which case a solution is
found. Once conflict occurs, we invoke do analysis to get a learnt
clause (Line ), which will be added to the clause database (Line ).
%Y.Chen An example might be necessary here, i.e. How is the learnt clause generated;
After that, we do backtracking until exactly one of the literals in
the learnt clause becomes unbounded, otherwise return UNSAT if
%R.Huang unbound is supposed to be `unbounded' I think
%R.Huang Also, what does "unbounded" here mean? Undefined? I don't quite understand; Make sure the term is commonly used.
conflict occurs in the top-level.

In the next section, we will discuss the DPLL-OPT algorithm, which
is developed based on the advances of the state-of-art SAT solving
algorithms.

\subsection{The DPLL-OPT algorithm}

The standard DPLL algorithm stops whenever a satisfying solution is
found. DPLL-OPT searches the whole space and find out the one with
the minimum action-cost. This optimization problem is defined as
follows:

Given a planning problem, we have a SAT formulation for each
particular makespan. Suppose this formulation has $n$ variables
$(x_1,x_2,\dots,x_n)$ and denote a valid configuration as
$V=(v_1,v_2,\dots,v_n),v_i\in\{true, false\}$, DPLL-OPT minimizes
the objective:
$$ cost(V) = \sum_{i=1}^{n}{c_iv_i}$$, in which $v_i=1$ if
variable $v_i$ is true, otherwise $v_i=0$.

The SAT encoding has three different types of variables:
 fact, action and dummy action.
Each action variable has a non-negative integer as its cost.  The
cost of both dummy actions and facts are 0. In this paper,
 we optimize the number of actions, meaning each action has the
 same cost. That is to say, the cost function $c_i$ is defined as:
$$
c_i = \left\{ \begin{array}{rl}
 1    & \mbox{ $v_i$ is of action  }  \\
 0    & \mbox{ $v_i$ is of dummy action or fact } \\
       \end{array} \right.
$$.


We mostly use the basic DPLL framework. However, in order to search
the whole space in reasonable time, we have two more sub-routines
addBlockClause() and pruning(). These two bounding technique helps
pruning those subspaces that cannot contain a solution. They
dramatically reduce the total search time.

%Firstly, we will
%introduce some control variables which are necessary in modified
%solver. And then, we will present the algorithm of these two
%procedures.

DISCUSS MORE ABOUT PRUNING!

%Y.Chen Draw an illustration or a picture for the reason why we need blocking clause and Pruning (in what sense it helps)

\subsubsection{Blocking Clauses}

Each time we found a solution, we add a corresponding blocking
clause to the clause database to make sure the later  searches
 do not repeat into the same search pathes.

Given a SAT problem with $n$ variables $(x_1,x_2,...,x_n)$, suppose
we have a valid solution $V=(v_1,v_2,\dots,v_n)
,v_i\in\{true,false\}$. We synthesize a blocking clause $M$ as:
$$M
=\bigvee_{i=0}^{n}{literal(V,i)}$$, such that $ literal(V,i) =
\left\{ \begin{array}{rl}
 \overline{x_i}     & \mbox{ $v_i = true$  }  \\
           x_i      & \mbox{ $v_i = false$ } \\
       \end{array} \right.
$.

For example, if the configuration of a solution for a 3-variable SAT
problem is $(x_1,x_2,x_3) = (true,false,true)$, then we have the
blocking clause $\overline{x_1}\vee x_2\vee \overline{x_3}$.


%R.Huang !!!!!!!!!!!!!!!!  IMPORTANT !!!!!!!!!!!!!!!!!!!!!!
%R.Huang Please formalize the definitions, rather than just giving an example.
%R.Huang Please write a definition for the Pruning Clause as well (along with an example)!!!! following what I wrote for Blocking clause
%R.Huang             Of course, this definition for blocking clause may not be perfect, but we NEED one anyway.(help me improve it)
%R.Huang It is necessary!!!!!!!!!!!! IMPORTANT!!

%***********************************************************************
%                     procedure solver_addBlockClause()
%***********************************************************************
\begin{algorithm}[t]
\label{addBlockClause} \linesnumbered\caption{addBlockClause($S$) }

\KwIn{blocking clause}

\KwOut{solution}

$num$++\;

$mini \leftarrow cost$\;
%R.Huang be concise and conservative in using variable name, it's not writing C code; You don't need to give them so long name,
%R.Huang because you have to explain them in the context sooner or later.

generate a solution\;

create a blocking clause $M$\;

%R.Huang Push it to where????????????????
veci$_-$push($M$)\;

$learnt\leftarrow$ analyze($M$)\;

record($learnt$)\;

do backtracking\;

\end{algorithm}

%R.Huang I suggest Procedure addBlockClause() and Pruning() should be merged into DPLL-OPT algorithm.
%R.Huang I think you must implemented it in this way, but presenting it in a different but more concise way is also a good idea.

Procedure addBlockClause() (Algorithm~\ref{addBlockClause}) is
invoked if the solver finds a
 new solution. It starts by increasing the counter of solution numbers $num$
 and updating the
 minimum cost $mini$ with the cost of the new solution $cost$. Then, a solution
will be generated. After that, we create a blocking clause, then add
it to the clause database to ensure that the solver will never
encounter with the same solution later. Using the blocking clause, a
learnt clause will be produced by analyze(), and added to the clause
database too. Finally, the procedure will undo assignments until
precisely one of the literals of the learnt clause becomes unbound.


\subsubsection{Pruning}


%R.Huang Add a formalized description of "Pruning"!!!!!!!!!! Rewrite this part;

%R.Huang Still the same suggestion, this algorithm is really short, without any complexity, why don't you just merge it into Algorithm#5?

After calling Procedure addBlockClause(), we continue to search for
other solutions with less cost and do not return until searched all
pathes. In our experiments on IPC5 domains, we found that there are
so many solutions (usually hundred thousands and most of then are
the same solutions because of the dummy actions) in just one
instance. As a result, we need to prune the search tree.


The procedure pruning() (Algorithm ~\ref{pruning}) can prune most of
the pathes. We invoke it when $curr_-costs$ is more than
$mini_-costs$. First of all, if current assignments are:
$x_1=true\wedge x_2=false\wedge x_3=free$, we will have the pruning
clause $\overline{x_1}\vee {x_2}$. After that, a learnt clause will
be produced by analyze() and we add it to the clause database.
Finally, we call the backtrack() to undo the assignments.


%***********************************************************************
% *******************      procedure pruning()      *************
%***********************************************************************
\begin{algorithm}[t]
\label{pruning} \linesnumbered \caption{pruning($S$)}

\KwIn{solver $S$}

%\KwOut{}

create a pruning clause $M$\;

$learnt\leftarrow$ analyze($M$)\;

add clause $learnt$ to the clause database\;

do backtracking\;

\end{algorithm}

Algorithm ~\ref{modifiedsolve} illustrates the DPLL-OPT algorithm.
We continue to search for other solutions if found a (or a less)
solution, and prune the search tree if necessary.
%R.Huang What does (or a less ) mean?
Once a satisfying solution with cost $c$ is found, we do not
propagate all literals in the propagation queue if $curr_-costs$ is
more than $mini_-costs$. We just stop propagating and return with no
conflict. We called this strategy active pruning, which is proved to
be very helpful in speeding up the searching.

%R.Huang I believe we can write more about the active pruning things here.


%Some important control variable in solver:
%
%\hspace{0.5cm}$int$ $solution_-num$;
%
%\hspace{0.5cm}$int$ $curr_-costs$;
%
%\hspace{0.5cm}$int$ $mini_-costs$;
%
%The variable $solution_-num$ represents the num of solutions which
%have been found. It will be increased in solver$_-$addBlockClause().
%
%In Procedure solve(), $curr_-costs$ increases when an action
%variable becomes true and decreases when a action variable
% changes from true to false or
% %free.
% %Q.lv sometimes change true to false, sometimes change true to free, both have to do decrease.
%to free.
% %R.Huang  What does "or free" mean?
%
%$mini_-costs$ represents the current minimal solution cost. It is
%initialized to $MAXCOST$ .

%***********************************************************************
% *******************  main procedure of modified-MiniSat   ************
%***********************************************************************
\begin{algorithm}[t]
\label{modifiedsolve} \linesnumbered \caption{ DPLL-OPT(CNF) }

\KwIn{SAT problem $S$}

\KwOut{a solution with minimum $cost$ }

initialize the solver\;

\While{ $true$ }{
    $conflict \leftarrow$ propagate()\;


    \eIf{$conflict$}{
        %\\-can't use eIf???\;
        %Q.Lv sometimes i can works, sometimes can't. so, what's wrong?
        $learnt \leftarrow$ analyze($conflict$)\;
        \eIf{top-level conflict found}{
            return $solution_-num > 0$ ? SAT:UNSAT\;
        }{
            record($learnt$)\;
            do backtracking\;
        }
    }{
        \eIf{$curr_-costs \geq mini_-costs$}{
            pruning()\;
        }{

            \eIf{all variables assigned}{
                addBlockClause()\;
%                \If{top-level}{
%                    return SAT\;
%                }
            }{
                decide()\;
            }
        }
    }
}
\end{algorithm}


\section{Experimental Results}

We remind that MaxPlan2 can only handle propositional STRIPS
domains, and among them, we considered the IPCs domains(including
depot, dirverlog, freecell,
%rovers,
%Q.Lv rovers in still in IPC5, so i think it's not necessary.
zenotravel domains of IPC3, airport, satellite domains of IPC4 and
pathways, pipesworld, rovers, storage, tpp, trucks domains of IPC5).
They are standard planning problems in which the plan not require
minimal total-costs. So, we define that the action's cost is always
equal to $1$ in MaxPlan2's SAT encoding which means the MaxPlan2's
returning plan's total-cost equal to the number of actions.

On the contrary, in this paper we focus on:

1. The reduction in the number of actions in the plan returned by
MaxPlan2 over MaxPlan~\cite{Chen:ICAPS-06}.

2. A comparison between MaxPlan, MaxPlan2, SGPlan and Fast-Downwrad
on the number of actions and makespan returned.

We ran all the experiments on a Linux desktop with a Pentium IV
2.20GHz (dual-core) processor and 1GB of RAM. The timeout is set to
1800s (the IPC5's time limit) for each instance and we set changed
the Algorithm~\ref{mainprocedure}'s 8 line that the solver will
search the next ten levels when searching for a solution. In the
plots, a point is missed if the solver does not find a plan for the
corresponding instance.

%Q.LV delete description of solving time, firstly we focus on costs and makespan.
% Then, we will discuss solving time in addition.
Figure~\ref{qualityfig} and Table~\ref{statbl} showed detailed
results on each instance that MaxPlan2 can solve. In
Figure~\ref{qualityfig}, we can see that MaxPlan2 generates plans
with less number of actions than MaxPlan does in most of instances
except Airport and Trucks.
%Q.Lv add some description of Figure~\ref{timefig} and Table~\ref{statbl}.
%In Figure~\ref{timefig} and
%Table~\ref{statbl}, we can see that MaxPlan2 can find the plan with
%minimal number of actions in the time which is 100 seconds less than
%MaxPlan's solve time in most of instances (71.15\%). The most
%important information of Table~\ref{statbl} is that in most of the
%instances(94.25\%), makespan of MaxPlan2 and Maxplan are the same.
Table~\ref{statbl} showed the statistic information MaxPlan
comparing with MaxPlan2. From this table, we can see that MaxPlan
and MaxPlan2 can solve 186(49.21\%) of all 378 instances, and in
94.09\% of these solvable instances, makespan of MaxPlan2 and
MaxPlan are the same. Further more, there is no instances which
makespan of MaxPlan2 is 3 more than MaxPlan. It means that we can
just search next three level when finding the first plan in
Algorithm~\ref{mainprocedure}.

\begin{figure*}[t]
  \centering
    \subfigure{\includegraphics[scale=0.46]{./experiments/depot/depot_quality.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/driverlog/driverlog_quality.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/freecell/freecell_quality.eps}}
%  \subfigure{\includegraphics[scale=0.46]{./experiments/RoversIPC3/rovers_quality.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/zenotravel/zenotravel_quality.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/airport/airport_quality.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/satellite/satellite_quality.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/TPP/tpp_quality.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/Storage/storage_quality.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/Pathways/pathways_quality.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/trucks/truck_quality.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/Rovers/rovers_quality.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/pipesworld/pipesworld_quality.eps}}
    \\
\caption{\label{qualityfig} Experimental results on IPCs domains.
Number of actions by Maxplan and Maxplan2.}
\end{figure*}


%Q.Lv deleted Rovers(IPC3) and the time information
\begin{table}[t]
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|}
\hline
    &      & \multicolumn{4}{|c|}{makespan of plan}\\
\cline{3-6}
 domain    &  tasks     &   +0  &   +1  &   +2  &   +3  \\
\hline
Depot       &   15/22   &   14  &   0   &   0   &   1   \\
Dirverlog   &   15/20   &   11  &   4   &   0   &   0   \\
Freecell    &   3/20    &   1   &   1   &   1   &   0   \\
%Rovers(IPC3) &  15/20  &   15  &   0   &   0   &   0   \\
Zenotravel  &   15/20   &   13  &   1   &   1   &   0   \\
\hline
Airport     &   38/50   &   38  &   0   &   0   &   0   \\
Satellite   &   17/36   &   17  &   0   &   0   &   0   \\
\hline
TPP         &   20/30   &   20  &   0   &   0   &   0   \\
Storage     &   15/30   &   13  &   0   &   2   &   0   \\
Pathways    &   7/30    &   7   &   0   &   0   &   0   \\
Trucks      &   3/30    &   3   &   0   &   0   &   0   \\
Rovers      &   30/40   &   30  &   0   &   0   &   0   \\
PipesWorld  &   8/50    &   8   &   0   &   0   &   0   \\
\hline
%total       &   398 &   201 &   143 &   190 &   6   &   4   &   1   \\
total       &   186/378 &   175 &   6   &   4   &   1   \\
\cline{2-6}
%percent     &      &   50.5\%   &   71.15\% &94.52\% &   2.98\%  &   1.99\%  &   0.49\%  \\
percentage(\%)     &   49.21   &   94.09 & 3.23   &     2.15 &   0.53  \\
 \hline
\end{tabular}
\caption{\label{statbl} The first column is the domain name of IPCs.
%the second column is the number of instances which can be solved by
%MaxPlan and MaxPlan2.
In the second column, ``x/y" indicates that MaxPlan(2) can solve x
instances which corresponding domain includes y instances.
%the third column is the number of
%instances MaxPlan2 can solve, the fourth column is the number of
%instances which the time of finding the plan with minimal number of
%actions returned by MaxPlan2 is 100 seconds less than MaxPlan.
The last four columns represent the number of instances which the
makespan of plan returned by MaxPlan2 compared with MaxPlan.}
\end{center}
\vspace*{-0.2in}
\end{table}


We also compare MaxPlan2 with SATPlan, SGPlan and Fast-Downward.
Table ~\ref{restbl} shows the results obtained. The first column is
of specific instances (which is given by ~\cite{Giu07}). Columns 2-6
contain the number of actions for MaxPlan, Maxplan2,
SATPlan$^{\prec}$(w), SATPlan$^{\prec}$(s), SGPlan and
Fast-Downward, respectively. A ``-" indicates that the corresponding
instance has not been solved in the given time limit
%Q.Lv
and a ``n/a" means we didn't get the corresponding data. The data of
this table for SATPlan and SGPlan is from ~\cite{Giu07}.

From the results, we can see that $(i)$MaxPlan2 can return plans
with the lower number of actions with respect to
SATPlan$^{\prec}$(w), SATPlan$^{\prec}$(s)
%Q.Lv
in all instances, and in most of instances,it also performs better
than Fast-Downward(except some instances in Rovers domian); $(ii)$
MaxPlan2 can return plans with lower makespan than SGPlan. So,
MaxPlan2 performs better than SATPlan, SGPlan and Fast-Downward on
these aspects.

There is still a shortage of Maxplan2: too much time overhead. Our
main idea of modifying MaxPlan in MiniSat-solver is to search all
possible assignments, which may lead to exceed the timeout bound.
%Q.Lv
In order to show this problem, we did the experiments again which
used the no changing Algorithm~\ref{mainprocedure} that only search
next three layers when finding a plan. In the results, MaxPlan2
stops the search in a lot of instances because of timeout even if
they have found some solutions. Table~\ref{stattimetbl} show the
detail information of running time of MaxPlan and MaxPlan2. In
Table~\ref{stattimetbl}, we can see that MaxPlan2 ran timeout in
$87.63\%$ instances even in which it have returned a plan with
minimal number of acions. What is gratifying is that $72.04\%$
instances which the time of finding the plan with minimal number of
actions returned by MaxPlan2 is 100 seconds less than MaxPlan. It
provides a possibility to improve the search efficiency of MaxPlan2.


\begin{figure*}[t]
  \centering
    \subfigure{\includegraphics[scale=0.46]{./experiments/depot/depot_time.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/driverlog/driverlog_time.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/freecell/freecell_time.eps}}
%\subfigure{\includegraphics[scale=0.46]{./experiments/RoversIPC3/rover_time.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/zenotravel/zenotravel_time.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/airport/airport_time.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/satellite/satellite_time.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/TPP/tpp_time.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/Storage/storage_time.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/Pathways/pathways_time.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/trucks/truck_time.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/Rovers/rover_time.eps}}
    \subfigure{\includegraphics[scale=0.46]{./experiments/pipesworld/pipesworld_time.eps}}
    \\
\caption{\label{timefig}
%Q.Lv add a line about total time of Maxplan2
Experimental results on IPCs domains. Comparison of solving time.
The line ``total-MP" represents the total solving time of MaxPlan,
the line ``mini-Mp2" represents the time of finding the plan with
minimal number of actions returned by MaxPlan2 and ``total-Mp2"
represents the total solving time of MaxPlan2.}
\end{figure*}

%Q.Lv add a table about solving time.
\begin{table}[t]
\begin{center}
\begin{tabular}{|l|c|c|c|}
\hline
%    &      & \multicolumn{4}{|c|}{makespan of plan}\\
%\cline{3-6}
 domain    &  tasks     &   ${\Delta}$time$<$100  &  timeout \\
\hline
Depot       &   15  &   9   &   15   \\
Dirverlog   &   15  &   13  &   15   \\
Freecell    &   3   &   3   &   3   \\
Zenotravel  &   15  &   10  &   13   \\
\hline
Airport     &   38  &   38  &   31   \\
Satellite   &   17  &   11  &   16  \\
\hline
TPP         &   20  &   12  &   16   \\
Storage     &   15  &   15  &   9   \\
Pathways    &   7   &   3   &   7   \\
Trucks      &   3   &   3   &   2    \\
Rovers      &   30  &   12  &   30   \\
PipesWorld  &   8   &   5   &   6   \\
\hline
%total       &   398 &   201 &   143 &   190 &   6   &   4   &   1   \\
total       &   186 &   134 &   163   \\
\cline{2-4}
%percent     &      &   50.5\%   &   71.15\% &94.52\% &   2.98\%  &   1.99\%  &   0.49\%  \\
percentage(\%)&     &   72.04   & 87.63    \\
 \hline
\end{tabular}
\caption{\label{stattimetbl} The first column is the domain name of
IPCs, and the second column is the number of instances which can be
solved by MaxPlan and MaxPlan2. The third column is the number of
instances which the time of finding the plan with minimal number of
actions returned by MaxPlan2 is 100 seconds less than MaxPlan. The
last column represent the number of instances which total run-time
of MaxPlan2 reaches the time-bound 1800 seconds.}
\end{center}
\vspace*{-0.2in}
\end{table}

\begin{table*}[t]
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|}
\hline
    &\multicolumn{6}{|c|}{number of actions} &\multicolumn{4}{|c|}{makespan} \\
\cline{2-11}
%       & MaxPlan   & MaxPlan2  & SATPlan$\prec$(w)  & SATPlan$\prec$(s)  & SGPlan   &   MaxPlan & MaxPlan2 & SATPlan & SGPlan \\
        &   MP  &   MP2 &   SPw &   SPs &   SGP &   FD &   MP  &   MP2 &   SP  &   SGP \\
\hline

Depot1      &   13  &   10  &   n/a &   n/a &   n/a &   10  &   5   &   8   &   n/a &   n/a \\
Depot2      &   22  &   16  &   n/a &   n/a &   n/a &   18  &   8   &   8   &   n/a &   n/a \\
Depot3      &   36  &   29  &   n/a &   n/a &   n/a &   114 &   12  &   12  &   n/a &   n/a \\
\hline
Driverlog1  &   18  &   7   &   8   &   8   &   7   &   8   &   6   &   7   &   6   &   7   \\
Driverlog2  &   25  &   19  &   n/a &   n/a &   n/a &   20  &   9   &   9   &   n/a &   n/a \\
Driverlog3  &   21  &   12  &   n/a &   n/a &   n/a &   15  &   7   &   7   &   n/a &   n/a \\
\hline
Freecell1   &   11  &   8   &   9   &   11  &   10  &   12  &   5   &   6   &   5   &   10  \\
Freecell2   &   18  &   15  &   -   &   18  &   14  &   16  &   5   &   6   &   8   &   14  \\
Freecell3   &   21  &   18  &   21  &   21  &   19  &   21  &   5   &   6   &   7   &   19  \\
\hline
Zenotravel2 &   7   &   6   &   6   &   6   &   8   &   6   &   5   &   5   &   5   &   8   \\
Zenotravel3 &   15  &   6   &   6   &   6   &   6   &   6   &   5   &   5   &   5   &   6   \\
Zenotravel4 &   16  &   8   &   11  &   11  &   13  &   9   &   5   &   7   &   5   &   13  \\
Zenotravel5 &   15  &   14  &   14  &   14  &   11  &   16  &   5   &   5   &   5   &   11  \\
Zenotravel6 &   15  &   12  &   12  &   12  &   13  &   14  &   5   &   5   &   5   &   13  \\
Zenotravel8 &   18  &   14  &   15  &   15  &   12  &   16  &   5   &   6   &   5   &   12  \\
Zenotravel9 &   29  &   23  &   -   &   -   &   23  &   22  &   6   &   6   &   6   &   23  \\
\hline
Airport7    &   41  &   41  &   41  &   41  &   41  &   43  &   21  &   21  &   21  &   41  \\
Airport9    &   71  &   71  &   -   &   71  &   73  &   75  &   27  &   27  &   27  &   73  \\
Airport12   &   39  &   39  &   39  &   39  &   39  &   39  &   21  &   21  &   21  &   39  \\
\hline
Satellite1  &   9   &   9   &   9   &   9   &   9   &   9   &   8   &   8   &   8   &   9   \\
Satellite2  &   23  &   13  &   -   &   13  &   13  &   22  &   12  &   12  &   12  &   13  \\
\hline
TPP4        &   14  &   14  &   14  &   14  &   14  &   14  &   5   &   5   &   5   &   14  \\
TPP5        &   23  &   19  &   19  &   19  &   19  &   19  &   7   &   7   &   7   &   19  \\
\hline
Storage5    &   11  &   8   &   9   &   9   &   8   &   9   &   6   &   8   &   6   &   8     \\
Storage6    &   11  &   8   &   9   &   9   &   10  &   9   &   6   &   8   &   6   &   10    \\
Storage7    &   14  &   14  &   14  &   14  &   14  &   14  &   14  &   14  &   14  &   14    \\
Storage8    &   14  &   12  &   12  &   12  &   13  &   14  &   8   &   8   &   8   &   13   \\
Storage9    &   16  &   12  &   12  &   12  &   11  &   12  &   7   &   7   &   7   &   11   \\
Storage10   &   18  &   18  &   -   &   18  &   18  &   18  &   18  &   18  &   18  &   18   \\
Storage11   &   22  &   18  &   -   &   18  &   17  &   20  &   11  &   11  &   11  &   17   \\
Storage12   &   24  &   18  &   -   &   20  &   17  &   20  &   9   &   9   &   9   &   17  \\
\hline
Pathways1   &   12  &   6   &   n/a &   n/a &   n/a &   6   &   5   &   5   &   n/a &   n/a \\
Pathways2   &   49  &   12  &   n/a &   n/a &   n/a &   12  &   7   &   7   &   n/a &   n/a \\
Pathways3   &   63  &   29  &   n/a &   n/a &   n/a &   18  &   7   &   7   &   n/a &   n/a \\
\hline
Trucks1     &   13  &   13  &   n/a &   n/a &   n/a &   15  &   11  &   11  &   n/a &   n/a \\
Trucks2     &   17  &   17  &   n/a &   n/a &   n/a &   18  &   14  &   14  &   n/a &   n/a \\
Trucks3     &   20  &   20  &   n/a &   n/a &   n/a &   24  &   16  &   16  &   n/a &   n/a \\
\hline
%Rovers1     &   13  &   10  &   n/a &   n/a &   n/a &   10  &   5   &   5   &   n/a &   n/a \\
%Rovers2     &   19  &   8   &   n/a &   n/a &   n/a &   8   &   4   &   4   &   n/a &   n/a \\
Rovers3     &   21  &   13  &   n/a &   n/a &   n/a &   12  &   7   &   7   &   n/a &   n/a \\
Rovers6     &   55  &   41  &   n/a &   n/a &   n/a &   38  &   7   &   7   &   n/a &   n/a \\
Rovers8     &   46  &   32  &   n/a &   n/a &   n/a &   26  &   7   &   7   &   n/a &   n/a \\
\hline
PipesWorld2 &   16  &   12  &   n/a &   n/a &   n/a &   -   &   10  &   10  &   n/a &   n/a \\
PipesWorld3 &   12  &   8   &   n/a &   n/a &   n/a &   -   &   6   &   6   &   n/a &   n/a \\
PipesWorld5 &   11  &   8   &   n/a &   n/a &   n/a &   -   &   6   &   6   &   n/a &   n/a \\
\hline
\end{tabular}
\caption{\label{restbl} The overall results of MaxPlan(MP),
MaxPlan2(MP2), SATPlan$^{\prec}$(w)(SPw), SATPlan$^{\prec}$(s)(SPs)
, SGPlan(SGP) and Fast-Downward(FD) on IPCs domains. The results are
shown in terms of the number of actions and makespan returned by
each solver.}
\end{center}
\vspace*{-0.2in}
\end{table*}

\section{Conclusions}
In this paper we presented a SAT based planning algorithm for
minimizing action cost solutions, MaxPlan2, which makes a
significant improvement of MaxPlan related to total-costs in the
returned plan. We conducted experiments on benchmarks from IPC5 and
showed that significant improvement in solution quality can be
obtained.
%As a future work, we will focus on solving the timeout
%problem.
%R.Huang This sentence sounds weird...



\bibliographystyle{aaai}
\bibliography{aaai}
\end{document}
